#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int palindromePartition(string s, int k)
    {
        int n = s.size();
        // 使用f[i][j]表示 s: [i,j] 转变为回文串的代价
        // 时间 n^2
        vector<vector<int>> cost(n, vector<int>(n, 0));
        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                cost[i][j] = cost[i + 1][j - 1] + (s[i]!=s[j]);
            }
        }
        // 使用 dp[i][j] 表示 0 - j 划分为 i+1 个 子串 修改的cost
        // j >= i
        // w >= i-1
        // dp[i][j] = min_{0 <= w < j} dp[i-1][w] + cost[w][j]
        // j > w
        
        // dp[0][j] = cost[0][j]
        // vector<vector<int>> dp(k, vector<int>(n,0));
        vector<int> dp(cost[0]);
        for(int i = 1; i < k; ++i){
            for(int j = n - 1; j >= i; --j){
                int mincost = 0x3f3f3f3f;
                for(int w = j - 1; w >= i-1; --w){
                    mincost = min(mincost, cost[w+1][j]+dp[w]);
                }
                dp[j] = mincost;
            }
        }
        return dp[n-1];
    }
};

int main()
{

    // system("pause");
    return 0;
}
